package labuladong.leetcode.editor.cn._01linkedlist.ch01;

import labuladong.leetcode.editor.cn._00bean.ListNode;

import static labuladong.leetcode.editor.cn._00utils.LinkedListUtils.build;
import static labuladong.leetcode.editor.cn._00utils.LinkedListUtils.print;

public class _92_ReverseLinkedListIi {

    //leetcode submit region begin(Prohibit modification and deletion)

    /**
     * Definition for singly-linked list.
     * public class ListNode {
     * int val;
     * ListNode next;
     * ListNode() {}
     * ListNode(int val) { this.val = val; }
     * ListNode(int val, ListNode next) { this.val = val; this.next = next; }
     * }
     */
    class Solution {
        public ListNode reverseBetween(ListNode head, int m, int n) {
            // base case
            if (m == 1) {
                return reverseN(head, n);
            }
            // 前进到反转的起点触发 base case
            head.next = reverseBetween(head.next, m - 1, n - 1);
            return head;
        }

        ListNode successor = null; // 后驱节点

        // 反转以 head 为起点的 n 个节点，返回新的头结点
        ListNode reverseN(ListNode head, int n) {
            if (n == 1) {
                // 记录第 n + 1 个节点
                successor = head.next;
                return head;
            }
            // 以 head.next 为起点，需要反转前 n - 1 个节点
            ListNode last = reverseN(head.next, n - 1);

            head.next.next = head;
            // 让反转之后的 head 节点和后面的节点连起来
            head.next = successor;
            return last;
        }
    }
//leetcode submit region end(Prohibit modification and deletion)

    public static void main(String[] args) {
        Solution solution = new _92_ReverseLinkedListIi().new Solution();

        int[] nums = {1, 2, 3, 4, 5};
        ListNode head = build(nums);
        print(head);

        ListNode res = solution.reverseBetween(head, 2, 4);
        print(res);
    }
}
